home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / list / RCS / List.g,v < prev    next >
Text File  |  1989-06-12  |  7KB  |  221 lines
  1. head     1.2;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @@;
  7.  
  8.  
  9. 1.2
  10. date     89.06.12.16.59.17;  author shirriff;  state Exp;
  11. branches ;
  12. next     1.1;
  13.  
  14. 1.1
  15. date     88.12.30.15.20.35;  author ouster;  state Exp;
  16. branches ;
  17. next     ;
  18.  
  19.  
  20. desc
  21. @@
  22.  
  23.  
  24. 1.2
  25. log
  26. @added List_ListInsert
  27. @
  28. text
  29. @' $Header: /sprite/src/lib/c/list/RCS/List.g,v 1.1 88/12/30 15:20:35 ouster Exp Locker: shirriff $ SPRITE (Berkeley)
  30. .so \*(]ltmac.sprite
  31. .HS List lib
  32. .BS
  33. .SH NAME
  34. List \- overview of circular linked list routines.
  35. .SH SYNOPSIS
  36. .nf
  37. \fB#include <list.h>\fR
  38. .sp
  39. \fBList_Init\fR(\fIheaderPtr\fP)
  40. \fBList_InitElement\fR(\fIitemPtr\fP)
  41. \fBList_Insert\fR(\fIitemPtr\fP, \fIdestPtr\fP)
  42. \fBList_ListInsert\fR(\fIheaderPtr\fP, \fIdestPtr\fP)
  43. \fBList_Remove\fR(\fIitemPtr\fP)
  44. \fBList_Move\fR(\fIitemPtr\fP, \fIdestPtr\fP)
  45. .sp
  46. \fBLIST_AFTER\fR(\fIitemPtr\fP)
  47. \fBLIST_BEFORE\fR(\fIitemPtr\fP)
  48. \fBLIST_ATFRONT\fR(\fIheaderPtr\fP)
  49. \fBLIST_ATREAR\fR(\fIheaderPtr\fP)
  50. .sp
  51. \fBLIST_FORALL\fR(\fIheaderPtr\fP, \fIitemPtr\fP)
  52. .sp
  53. \fBList_IsEmpty\fR\fR\fB(\fIheaderPtr\fP)
  54. \fBList_IsAtEnd\fR(\fIheaderPtr\fP, \fIitemPtr\fP)
  55. \fBList_First\fR\fR\fB(\fIheaderPtr\fP)
  56. \fBList_Last\fR\fR\fB(\fIheaderPtr\fP)
  57. \fBList_Prev\fR\fR\fB(\fIitemPtr\fP)
  58. \fBList_Next\fR\fR\fB(\fIitemPtr\fP)
  59. .SH ARGUMENTS
  60. .AS List_Links *headerPtr in
  61. .AP List_Links *headerPtr in
  62. Pointer to the header of a list.
  63. .AP List_Links *itemPtr in 
  64. Pointer to a member of a list (possibly the header).
  65. .AP List_Links *destPtr in 
  66. Pointer to the member after which to insert or move another member.
  67. .BE
  68.  
  69. .SH INTRODUCTION
  70. .PP
  71. The \fBList_\fR\ routines define the ``list'' abstraction, 
  72. which enables one to link
  73. together arbitrary data structures.  Lists are doubly-linked and
  74. circular.  A list contains a header followed by its real members, if
  75. any.  (An empty list therefore consists of a single element, the
  76. header,  whose \fInextPtr\fR and \fIprevPtr\fR fields point to itself).
  77. To refer
  78. to a list as a whole, the user keeps a pointer to the header; that
  79. header is initialized by a call to \fBList_Init()\fR, which
  80. creates an empty
  81. list given a pointer to a List_Links structure (described below).
  82. .PP
  83. The links are contained in a two-element structure called List_Links.
  84. A list joins List_Links records (that is, each List_Links structure
  85. points to other List_Links structures), but if the List_Links is the
  86. first field within a larger structure, then the larger structures are
  87. effectively linked together as shown in Figure 1.
  88. .if t \{
  89. .bp
  90. .sp 2
  91. .GS C
  92. file fig.g
  93. width 5i
  94. .GE
  95. .\}
  96. .PP
  97. A typical structure might be something like:
  98.  
  99. .nf
  100.      typedef struct {
  101.                  List_Links links;
  102.                  char ch;
  103.                  int flags;
  104.      } EditChar;
  105. .fi
  106. .LP
  107. It is possible to link structures through List_Links fields that are
  108. not at the beginning of the larger structure, but it is then necessary
  109. to perform an additional pointer indirection to find the beginning of
  110. the larger 
  111. structure, given a pointer to some point within it.  The easiest way to do 
  112. this is to define a structure that contains a List_Links field and a pointer
  113. to the larger structure, such as:
  114. .nf
  115.      typedef struct {
  116.                  List_Links links;
  117.                  LargeStruct *structPtr;
  118.      } LargeStructLink;
  119. .fi
  120. .LP
  121. By including a ``LargeStructLink'' within a ``LargeStruct'' and setting the
  122. structPtr field of the LargeStructLink to point to the LargeStruct
  123. itself, LargeStruct structures may be linked together in a list
  124. that is contained in the middle of the structure rather than the beginning.
  125.  
  126. .SH USAGE
  127. .PP
  128. After a list has been initialized by calling \fBList_Init\fR, elements may
  129. be inserted, deleted, or moved within the list.  
  130. Before an element is inserted in a list for the first time it must
  131. be initialized by calling the routine \fBList_InitElement\fR.  To insert a
  132. List_Links element into a list, \fBList_Insert\fR is called with two
  133. arguments.  The first argument is a pointer to the structure to be
  134. inserted into a list, and the second argument is a pointer to the list
  135. member after which it is to be inserted.  Typically, the following
  136. macros are used to select the insertion point or the destination of a
  137. \fBList_Move\fR:
  138. .IP
  139. .RS
  140. .IP "\(bu \fBLIST_BEFORE\fR(\fIitemPtr\fR)" 30
  141. Insert the element before \fI*itemPtr\fR.
  142. .IP "\(bu \fBLIST_AFTER\fR(\fIitemPtr\fR)" 30
  143. Insert the element after \fI*itemPtr\fR.
  144. .IP "\(bu \fBLIST_ATFRONT\fR(\fIheaderPtr\fR)" 30
  145. Insert the element at the front of the list.
  146. .IP "\(bu \fBLIST_ATREAR\fR(\fIheaderPtr\fR)" 30
  147. Insert the element at the end of the list.
  148. .RE
  149. .PP
  150. .VS
  151. To insert a list into another list, call \fBList_ListInsert\fR with the
  152. header of the list to be inserted and a pointer to the member of the second
  153. list after which the first list is to be inserted.  After calling
  154. \fBList_ListInsert\fP, the header of the first list is no longer valid
  155. and may be destroyed.
  156. .VE
  157. .PP
  158. To remove a structure from a list, call \fBList_Remove\fR with a
  159. pointer to the structure to be removed.  
  160. To move a structure, call \fBList_Move\fR with two arguments: a pointer to
  161. the structure to be moved, and a pointer to the structure after which
  162. it is to be placed.  \fBList_Move\fR(\fIitemPtr\fR, \fIdestPtr\fR) is therefore
  163. equivalent to \fBList_Remove\fR(\fIitemPtr\fR) followed by \fBList_Insert\fR(\fIitemPtr\fR,
  164. \fIdestPtr\fR).
  165.  
  166. .SH ADDITIONAL UTILITIES
  167. .PP
  168. Several other macros are available for the manipulation of List_Links.
  169. \fBLIST_FORALL\fR(\fIheaderPtr\fR, \fIitemPtr\fR) is used to step through each element
  170. in the list pointed to by headerPtr, setting itemPtr to point to each
  171. element in turn.  \fBLIST_FORALL\fR is used typically by casting \fIitemPtr\fR as
  172. a pointer to the entire structure, as in:
  173. .nf
  174.     List_Links *headerPtr;    /* pointer to head of existing list */
  175.     List_Links *itemPtr;    /* place-holder during loop */
  176.     EditChar   *charPtr;    /* pointer to entire EditChar structure */
  177.  
  178.     LIST_FORALL(headerPtr, itemPtr) {
  179.         charPtr = (EditChar *) itemPtr;
  180.         /* operations using charPtr */
  181.     }
  182. .fi
  183. .PP
  184. The following macros may be useful to those who use List_Links at a
  185. ``lower'' level than looping through an entire list:
  186. .RS
  187. .IP "\(bu \fBList_IsEmpty\fR(\fIheaderPtr\fR) " 30
  188. returns TRUE if \fIheaderPtr\fR points to an empty
  189. list.
  190. .IP "\(bu \fBList_IsAtEnd\fR(\fIheaderPtr\fR, \fIitemPtr\fR)" 30
  191. returns TRUE if \fIitemPtr\fR is
  192. past the end of the list; i.e., it points to the header.
  193. .IP "\(bu \fBList_First\fR(\fIheaderPtr\fR) " 30
  194. .IP "\(bu \fBList_Last\fR(\fIheaderPtr\fR) " 30
  195. \fBList_First\fR returns the first member in a list, and
  196. \fBList_Last\fR returns the last member.  If the list is empty,
  197. the header is considered to be the first and last member.
  198. .IP "\(bu \fBList_Prev\fR(\fIitemPtr\fR) " 30
  199. returns a pointer to the member preceding the given
  200. member in its list.  
  201. .IP "\(bu \fBList_Next\fR(\fIitemPtr\fR)" 30
  202. returns the next
  203. member of the list.
  204. .RE
  205. .SH KEYWORDS
  206. list, linked, circular, List_Links, data structures
  207. @
  208.  
  209.  
  210. 1.1
  211. log
  212. @Initial revision
  213. @
  214. text
  215. @d1 1
  216. a1 1
  217. ' $Header: List,v 1.3 87/06/08 18:42:31 nelson Exp $ SPRITE (Berkeley)
  218. d14 1
  219. d121 8
  220. @
  221.